package com.kaifamiao.month04.day12;

public class MaxLengthSubString {

    public String subString(String str) {
        String maxStr = "";
        StringBuilder leftStr = new StringBuilder();
        StringBuilder rightStr = new StringBuilder();
        int max = 0,i = 0,bound = str.length();
        while(i <= (str.length() >> 1)) {
            int rightIndex = str.lastIndexOf(str.charAt(i),bound);
            if(rightIndex == i) {
                i++;
                bound = str.length();
                continue;
            }
            for(int left = i,right = rightIndex;right != 0 && left <= (right + left) >> 1 ;right--) {
                if(str.charAt(right) == str.charAt(left)) {
                    //匹配成功
                    if(left < right) {
                        leftStr.append(str.charAt(left));
                        rightStr.insert(0, str.charAt(right));
                    }
                    if(left == right) {
                        leftStr.append(str.charAt(left));
                        bound = str.length();
                    }
                    left ++;
                }else {
                    //匹配失败
                    leftStr = new StringBuilder();
                    rightStr = new StringBuilder();
                    bound = rightIndex - 1;
                    rightIndex = str.lastIndexOf(str.charAt(i),bound);
                    i--;
                    break;
                }
            }
            String temp =  leftStr + rightStr.toString();
            if(max < temp.length()) {
                max = temp.length();
                maxStr = temp;
                bound = str.length();
            }
            leftStr = new StringBuilder();
            rightStr = new StringBuilder();
            i++;
        }
        return maxStr;
    }

    public static void main(String[] args) {
        MaxLengthSubString max = new MaxLengthSubString();
        System.out.println(max.subString("abcbcba"));
    }
}
